#include "rbtree.h"
#include<unordered_map>
#include<unordered_set>

template<class T>
void RBT::RBNode<T>::left_rotate(RBNode<T>*N){
    if(N->right){
        RBNode<T>*temp=N;
        N=N->right;
        if(N->left){
            temp->right=N->left;
        }
        N->left=temp;
    }
}
template<class T>
void RBT::RBNode<T>::right_rotate(RBNode<T>*N){
    if(N->left){
        RBNode<T>*temp=N;
        N=N->left;
        if(N->right){
            temp->left=N->right;
        }
        N->right=temp;
    }
}

template<class T>
void RBT::RBTree<T>::rb_insert(T val){
    RBNode<T>*n=this->root;
    RBNode<T>*father=nullptr;
    while(n){
        father=n;
        if(n->val>val)
            n=n->left;
        else
            n=n->right;
    }
    n=new RBNode<T>(val,RBT::red,father);
    this->recolor(n);
}


template<class T>
void RBT::RBTree<T>::insert_recolor(RBNode<T>*node){
    if(!node->father){
        node->color=black;//根节点设为黑色直接返回
        return ;
    }
    if(node->father->color==black)
        return;//父节点是黑色直接返回
    RBNode<T>*grandpa=node->father->father;

    if(node->father==grandpa->left){ //父亲是左子树
        if(grandpa->right&&grandpa->right->color==red){//叔节点是红色
            node->father->color=black;
            grandpa->right->color=black;
            grandpa->color=red;
            insert_recolor(grandpa);
        }else{//叔节点是黑色
            if(node==node->father->right){//是父亲的右子树
                RBNode<T>::right_rotate(node->father);
                insert_recolor(node->father);
            }else {//是父亲的左子树
                node->father->color=black;
                grandpa->color=red;
                insert_recolor(grandpa);
            }
        }
    }else{//父亲是右子树，和上面成镜像关系
        if(grandpa->left&&grandpa->left->color==red){
            node->father->color=black;
            grandpa->left->color=black;
            grandpa->color=red;
            insert_recolor(grandpa);
        }else{
            if(node==node->father->left){
                RBNode<T>::right_rotate(node->father);
                insert_recolor(node->father);
            }else {
                node->father->color=black;
                grandpa->color=red;
                insert_recolor(grandpa);
            }
        }
    }
}

template<class T>
RBT::RBNode<T>* RBT::RBTree<T>::rb_search(T val){
    RBNode<T>*search=this->root;
    while (search&&search->val!=val) {
        if(search->val>val)
            search=search->left;
        else
            search=search->right;
    }
    return search;
}

template<class T>
void RBT::RBTree<T>::rb_delete(T val){
    RBNode<T>*curr=this->rb_search(val);
    if(!curr)
        return ;
    
    while(curr->left||curr->right){ // 是否需要while？
        if(curr->right&&curr->left){ // 有两个子节点，使用后继节点替换删除
            curr=curr->right;
            curr->father->replace(curr);
            while(curr->left){
                curr=curr->left;
                curr->father->replace(curr);
            }
        }

        if(curr->left){ // 只有左节点，使用左节点替换删除
            curr=curr->left;
            curr->father->replace(curr);
        }else if(curr->right){ // 只有右节点，使用右节点替换删除
            curr=curr->right;
            curr->father->replace(curr);
        }
    }

    if(curr->father){
        if(curr->color==black){
            delete_recolor(curr);
        }

        if(curr->father->left==curr)
            curr->father->left=nullptr;
        else
            curr->father->right=nullptr;
        delete curr;
        curr=nullptr;
    }else {
        delete this->root;
        this->root=nullptr;
    }
}

template<class T>
void RBT::RBTree<T>::delete_recolor(RBNode<T>*node){
    
}